import java.sql.Connection;
import java.util.*;
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class test{
    public static void hello(){
        System.out.println("hello");
    }
}
class A{
    A(){
        System.out.println("a");
    }
}
class B extends A {

}
class C extends B{

}
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}
public class project{
    TreeNode bool=null;
    TreeNode node=null;
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        dfs(root,p);
        return node;
    }
    public void dfs(TreeNode root,TreeNode p){
        if(root==null){
            return;
        }
        dfs(root.left,p);
        if(bool==p){
            node=root;
        }
        bool=root;
        dfs(root.right,p);
    }

















//    public static void main(String[] args) {
//        new project();
//        new A();
//    }











//    public int ame(){
//        static int i=0;
//        i++;
//        return i;
//    }
//    public static boolean isadmin(String s){
//        return s.toLowerCase()=="admin";
//    }
//    public static void main(String[] args) {
//        System.out.println(isadmin("Admin"));
////        test t=null;
////        t.hello();
//    }








    public ListNode reverseEvenLengthGroups(ListNode head) {
        ListNode cur=head;
        int count=0;
        int base=1;
        ListNode prev=head;
        ListNode start=head;
        ListNode next=head;
        while (cur!=null){
            count++;
            if(count==base){
                if(count%2==0){
                    next=cur.next;
                    cur.next=null;
                    start=prev.next;
                    prev.next=reversal(start);
                    start.next=next;
                    cur=start;
                }
                count=0;
                prev=cur;
                base++;
            }
            cur=cur.next;
        }
        if(count%2==0){
            prev.next=reversal(prev.next);
        }
        return head;
    }
    public ListNode reversal(ListNode node){
        ListNode prev=null;
        while (node!=null){
            ListNode nodeNext=node.next;
            node.next=prev;
            prev=node;
            node=nodeNext;
        }
        return prev;
    }















    public int findMinDifference(List<String> timePoints) {
        if (timePoints.size() > 60 * 24) {
            return 0;
        }
        List<Integer> list = new ArrayList<>();
        for (String s : timePoints) {
            String[] str = s.split(":");
            list.add(Integer.parseInt(str[0]) * 60 + Integer.parseInt(str[1]));
        }
        Collections.sort(list);
        list.add(list.get(0) + 24 * 60);
        int min = 24 * 60;
        for (int i = 1; i < list.size(); i++) {
            min = Math.min(min, list.get(i) - list.get(i - 1));
        }
        return min;
    }














    public int dayOfYear(String date) {
        int[] arr = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
        int year = Integer.parseInt(date.substring(0, 4));
        int moth = Integer.parseInt(date.substring(5, 7));
        int day = Integer.parseInt(date.substring(8));
        if (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) {
            arr[1]++;
        }
        int sum = day;
        for (int i = 0; i < moth - 1; i++) {
            sum += arr[i];
        }
        return sum;
    }











    public int countCharacters(String[] words, String chars) {
        int[] arrChars = new int[26];
        for (char ch : chars.toCharArray()) {
            arrChars[ch - 'a']++;
        }
        int len = 0;
        boolean bool = true;
        for (String str : words) {
            bool = true;
            int[] arrWords = new int[26];
            for (char ch : str.toCharArray()) {
                arrWords[ch - 'a']++;
            }
            for (int i = 0; i < 26; i++) {
                if (arrWords[i] > arrChars[i]) {
                    bool = false;
                    break;
                }
            }
            if (bool) {
                len += str.length();
            }
        }
        return len;
    }










    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int val : stones) {
            queue.offer(val);
        }
        while (queue.size() > 1) {
            int tmp = queue.poll() - queue.poll();
            queue.offer(tmp);
        }
        return queue.peek();
    }











    public boolean CheckPermutation(String s1, String s2) {
        int[] arr = new int[26];
        for (char ch : s1.toCharArray()) {
            arr[ch - 'a']++;
        }
        for (char ch : s2.toCharArray()) {
            if (arr[ch - 'a'] < 1) {
                return false;
            }
            arr[ch - 'a']--;
        }
        return true;
    }
}







class Bank {
    public long[] balance;
    public int n=0;
    public Bank(long[] balance) {
        this.balance=balance;
        this.n=balance.length;
    }

    public boolean transfer(int account1, int account2, long money) {
        if(account1-1>=0&&account1-1<n&&account2-1>=0&&account2-1<n&&money<=balance[account1-1]){
            balance[account1-1]-=money;
            balance[account2-1]+=money;
            return true;
        }
        return false;
    }

    public boolean deposit(int account, long money) {
        if(account-1>=0&&account-1<n){
            balance[account-1]+=money;
            return true;
        }
        return false;
    }

    public boolean withdraw(int account, long money) {
        if(account-1>=0&&account-1<n&&balance[account-1]>=money){
            balance[account-1]-=money;
            return true;
        }
        return false;
    }
}